package tree;

/**
 * @author : Rookie
 * @description :
 * @date : 2023/10/29
 */
public class BinarySearchTreeDelete {

    public static void main(String[] args) {
        int[] tree = new int[] {3,2,7,1,-1,5,9,-1,-1,-1,-1,4,6,8,10};
        TreeNode root = BinaryTreeUtil.buildTree(tree);
        System.out.println("========删除节点之前========");
        BinaryTreeUtil.Traversal.sequenceTraversal(root);
        int key = 3;
        TreeNode newRoot = delete(root, key);
        System.out.println("\n========删除节点之后========");
        BinaryTreeUtil.Traversal.sequenceTraversal(newRoot);
    }

    private static TreeNode delete(TreeNode root,int key) {
        // 如果没找到要删除的节点
        if (root == null) {
            return null;
        }
        // 当前节点是要删除的节点
        if (root.element == key) {
            // 叶子节点
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left != null && root.right == null) {
                // 左孩子不为空，右孩子为空情况
                return root.left;
            } else if (root.left == null && root.right != null) {
                // 左孩子为空，右孩子不为空的情况
                return root.right;
            } else {
                // 左右孩子都不为空
                TreeNode node = getMin(root.right);
                // 将左子树拼接到右子树最小节点下
                node.left = root.left;
                // 返回右子树
                return root.right;
            }
        } else if (root.element > key) {
            root.left = delete(root.left,key);
        } else {
            root.right = delete(root.right,key);
        }
        return root;
    }

    /**
     * 查找右子树中最左下的节点
     * @param root
     * @return
     */
    private static TreeNode getMin(TreeNode root) {
        TreeNode curr = root;
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr;
    }
}
